9 задание ОГЭ по информатике
Тема: "Анализирование информации, представленной в виде схем"
Это задание проверяет ваше умение анализировать информацию, представленную в виде схем (графов). Достаточно похожее задание было у нас под номером 4. Только там мы анализировали информацию, представленную в виде таблиц, и сами преобразовывали её в виде графа (дерева). Такое же задание есть и в ЕГЭ, только немного посложнее, но зная общий алгоритм решения, не вызовет никаких сложностей.
Общий вид задания такой. Даны населенные пункты, между некоторыми есть дороги. Двигаться можно только в указанном направлении. Необходимо посчитать количество всевозможных путей из одно пункта в другой.
Мы будем использовать метод динамического программирования. Суть его в том, что мы постепенно из начального пункта до конечного будем получать промежуточные результаты для каждого пункта. И в результате получим ответ для конечного пункта.
Внимание! Ни в коем случае не решаем данное задание визуальным поиском!
Перейдем непосредственно к решению.
Задание 1.
На рисунке - схема дорог, связывающих города A, B, C, D, E, F, G и H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город H?
Решение:
Начнем последовательно от пункта A анализировать граф.
Обозначим A = 1, так как попасть в пункт A есть 1 способ (мы там находимся).
Далее начнем по порядку записывать все пункты и выявлять откуда в него мы можем прийти.
В пункт B мы можем попасть только из A, значит: B = A = 1. Это говорит нам о том, что попасть в пункт B можно единственным способом (из пункта A)
В пункт C мы можем попасть только из A, значит C = A = 1.
В пункт D мы можем попасть из A и C, значит D = A + C = 1 + 1 = 2.
В пункт E мы можем попасть из A и B, значит E = A + B = 1 + 1 = 2.
В пункт F мы можем попасть из D и E, значит F = D + E = 2 + 2 = 4. (Двумя способами мы можем попасть в D и двумя способами в E, всего попасть в F существует 4 способа).
В пункт G мы можем попасть из D, значит G = D = 2.
В пункт H мы можем попасть из F и G, значит H = F + G = 4 + 2 = 6.
В итоге мы нашли количество путей не только в конечный пункт H, но и во все промежуточные.
Ответ: 6
Внимание! Очень внимательно смотрим из какого пункта мы выходим и в какой нужно попасть (не всегда это крайний правый пункт)!
Задание 2.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К и Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?
Решение:
На первый взгляд кажется, что задание сильно сложнее, но мы опять пойдем по порядку.
A = 1
Б = А = 1
В = А + Б = 1 + 1 = 2
Не всегда мы можем по порядку анализировать пункты, например в пункт Г мы можем попасть из А и Д, поэтому в начале нужно определить количество путей в пункт Д
Д = А = 1
Г = А + Д = 1 + 1 = 2
Е = Б + В = 1 + 2 = 3
Ж = Г + Д = 2 + 1 = 3
З = Е + В + Г + Ж = 3 + 2 + 2 + 3 = 10
И = Е = 3
К = Ж = 3
Л = И + З + Ж + К = 3 + 10 + 3 + 3 = 19
Ответ: 19
Задание 3.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из пункта А в пункт К, не проходящих через пункт В?
Решение:
В этом задании появляется дополнительное условие: нужно посчитать только такие пути, которые не проходят через пункт В.
Поэтому сначала подредактируем наш граф.
Чтобы пути не проходили через В, мы не должны в этот пункт входить, и соответственно из него не будем и выходить, поэтому зачеркнем лишние пути:
Удобней всего перерисовать граф с учетом исправления и решать как обычно:
Теперь мы видим, что задача на самом деле очень легкая.
А = 1
Б = А = 1
Г = А = 1
Д = Б = 1
Е = Д = 1
И = Г + Е = 1 + 1 = 2
Ж = Д = 1
К = Ж + Д + Е + И = 1 + 1 + 1 + 2 = 5
Ответ: 5
Задание 4.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город И, проходящих через город В?
Решение:
Здесь уже условия выглядит по другому. Наоборот нам необходимо обязательно, чтобы путь проходил через пункт В.
Проанализируем наш граф.
В какой бы мы путь не пошли из А мы можем попасть в В. Но на этом нельзя останавливаться, идем дальше.
Из пункта Б мы не можем идти в Е, так как тогда мы пропустим пункт В.
Аналогично и Г мы не можем пойти в З, и из Д мы тоже не можем пойти в З.
Все, все остальные пути буду идти через В.
Перерисуем опять наш граф для удобного решения.
Решаем задачу как обычно.
А = 1
Б = А = 1
Д = А = 1
Г = А + Д = 1 + 1 = 2
В = Б + А + Г = 1 + 1 + 2 = 4
Е = В = 4
З = В = 4
Ж = Е + В + З = 4 + 4 + 4 = 12
И = Е + Ж + З = 4 + 12 + 4 = 20
Ответ: 20.
Задание 5.
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, 3, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М, проходящих через город Л, но не проходящих через город Е?
Решение:
В этом задании используются уже два условия, пути должны проходить через Л, и не проходить через Е.
Сначала рассмотрим условие, пути не проходят через пункт Е, значит мы не должны входить в него и соответственно не будем выходить из него:
Далее рассмотрим, что пути должны проходить через Л. Значит из пункта И мы можем пойти только в Л:
Перерисуем граф с учетом условий:
Решим стандартную задачу.
А = 1
Б = А = 1
Д = А = 1
Г = А + Д = 1 + 1 = 2
В = Б + А + Г = 1 + 1 + 2 = 4
З = В + Г + Д = 4 + 2 + 1 = 7
Ж = В + З = 4 + 7 = 11
И = Ж + З = 7 + 11 = 18
Л = И = 18
М = Л = 18
Ответ: 18.